﻿#include <iostream>

static int useNormalCoin(const int* coins, const size_t size, const int index, const int remain)
{
	if (remain == 0) return 1;
	if (remain < 0) return 0;
	if (index >= size) return 0;
	
	// 这个面值的硬币，用0个，1个，2个...
	int total = 0;
	for (int i = 0; remain - coins[index] * i >= 0; i++)
	{
		total += useNormalCoin(coins, size, index + 1, remain - coins[index] * i);
	}

	return total;
}

static int* useNormalCoinsDp = nullptr;

static int useNormalCoinDp(const int* coins, const size_t size, const int maxTotal, const int total)
{
	if (!useNormalCoinsDp)
	{
		useNormalCoinsDp = (int*)malloc(size * (maxTotal + 1) * sizeof(int));
		memset(useNormalCoinsDp, 0, size * (maxTotal + 1) * sizeof(int));

		for (int index = 0; index < size; index++)
		{
			useNormalCoinsDp[index] = 1;
		}

		int sum;
		for (int remain = 0; remain <= maxTotal; remain++)
		{
			for (int index = size - 1; index >= 0; index--)
			{
				sum = 0;
				//for (int i = 0; remain - coins[index] * i >= 0; i++)
				//{
				//	if (remain - coins[index] * i == 0)
				//		sum += 1;

				//	else if (index + 1 < size)
				//	{
				//		sum += useNormalCoinsDp[index + 1 + size * (remain - coins[index] * i)];
				//	}
				//}

				// 简化for循环，画index和remain的二维表来理解下面的代码
				// i=0 代表使用(index+1,remain)的数据，i=1到size-1等同于(index, remain-coins[index])的数据

				sum += (remain - coins[index] >= 0) ? useNormalCoinsDp[index + size * (remain - coins[index])] : 0;
				
				if (remain == 0)
				{
					++sum;
				}
				else if (index + 1 < size && remain > 0)
				{
					sum += useNormalCoinsDp[index + 1 + size * remain];
				}

				useNormalCoinsDp[index + size * remain] = sum;
			}
		}
	}

	return useNormalCoinsDp[size * total];
}

static int useCommemorativeCoin(const int* coins, const size_t size, const int index, const int remain)
{
	if (remain == 0) return 1;
	if (remain < 0) return 0;
	if (index >= size) return 0;

	int useCur = useCommemorativeCoin(coins, size, index + 1, remain - coins[index]);
	int notUseCur = useCommemorativeCoin(coins, size, index + 1, remain);
	return useCur + notUseCur;
}

static int* useCommemorativeCoinsDp = nullptr;

static int useCommemorativeCoinDp(const int* coins, const size_t size, const int maxTotal, const int total)
{
	if (!useCommemorativeCoinsDp)
	{
		useCommemorativeCoinsDp = (int*)malloc(size * (maxTotal + 1) * sizeof(int));
		memset(useCommemorativeCoinsDp, 0, size * (maxTotal + 1) * sizeof(int));

		for (int index = 0; index < size; index++)
		{
			useCommemorativeCoinsDp[index] = 1;
		}

		int useCur;
		int notUseCur;
		for (int remain = 0; remain <= maxTotal; remain++)
		{
			for (int index = size - 1; index >= 0; index--)
			{
				useCur = 0;
				if (remain - coins[index] == 0)
				{
					useCur = 1;
				}
				else if (remain - coins[index] > 0 && index + 1 < size)
				{
					useCur = useCommemorativeCoinsDp[index + 1 + size * (remain - coins[index])];
				}

				notUseCur = 0;
				if (remain == 0)
				{
					notUseCur = 1;
				}
				else if (index + 1 < size)
				{
					notUseCur = useCommemorativeCoinsDp[index + 1 + size * remain];
				}

				useCommemorativeCoinsDp[index + size * remain] = useCur + notUseCur;
			}
		}
	}

	return useCommemorativeCoinsDp[size * total];
}

static void test()
{
	int normalCoins[] = { 1,2,5 };
	int normalCoinsCount = sizeof(normalCoins) / sizeof(int);

	int commemorativeCoins[] = { 1,2,2,5 };
	int commemorativeCoinsCount = sizeof(commemorativeCoins) / sizeof(int);

	int targetValue = 16;

	int a = useNormalCoin(normalCoins, normalCoinsCount, 0, targetValue);
	int b = useNormalCoinDp(normalCoins, normalCoinsCount, targetValue, targetValue);
	printf("a=%d,b=%d\n", a, b);

	int c = useCommemorativeCoin(commemorativeCoins, commemorativeCoinsCount, 0, targetValue);
	int d = useCommemorativeCoinDp(commemorativeCoins, commemorativeCoinsCount, targetValue, targetValue);
	printf("c=%d,d=%d\n", c, d);
}

/**
 * 现在有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚；后n2种为纪念币，每种最多只能取1枚。每种硬币有一个面值，问能用多少种方法，拼出m的面值？
 */
int main_twoKindOfCoinsToGetOutOfTheFaceValue()
{
	int normalCoins[] = { 1,2,5 };
	int normalCoinsCount = sizeof(normalCoins) / sizeof(int);

	int commemorativeCoins[] = {1,2,2,5};
	int commemorativeCoinsCount = sizeof(commemorativeCoins) / sizeof(int);

	int targetValue = 20;

	//test();

	int normalCount;
	int commemorativeCount;
	int total = 0;
	for (int normalValue = 0; normalValue <= targetValue; normalValue++)
	{
		normalCount = useNormalCoin(normalCoins, normalCoinsCount, 0, normalValue);
		commemorativeCount = useCommemorativeCoin(commemorativeCoins, commemorativeCoinsCount, 0, targetValue - normalValue);
		total += normalCount * commemorativeCount;
	}

	printf("%d\n", total);

	total = 0;
	for (int normalValue = 0; normalValue <= targetValue; normalValue++)
	{
		normalCount = useNormalCoinDp(normalCoins, normalCoinsCount, targetValue, normalValue);
		commemorativeCount = useCommemorativeCoinDp(commemorativeCoins, commemorativeCoinsCount, targetValue, targetValue - normalValue);
		total += normalCount * commemorativeCount;
	}

	printf("%d\n", total);

	if (useNormalCoinsDp)
	{
		free(useNormalCoinsDp);
		useNormalCoinsDp = nullptr;
	}

	if (useCommemorativeCoinsDp)
	{
		free(useCommemorativeCoinsDp);
		useCommemorativeCoinsDp = nullptr;
	}

	return 0;
}